1. Field of the Invention
The present invention relates to wireless localization technology (e.g., estimating the location of a mobile terminal in a data communication network). More particularly, the present invention relates to localization using a linear least squares (LLS) or maximum likelihood (ML) estimator.
2. Discussion of the Related Art
Numerous techniques have been developed to resolve a position of a mobile terminal (MT) from a set of measured distances. If the variance of distance measurements at each MT is available, the maximum likelihood (ML) solution can be obtained using a weighted non-linear least squares (WNLS) approach. (See, e.g., the article “Overview of Radiolocation in CDMA Cellular Systems” (“Caffery I”), by J. J. Caffery and G. L. Stuber, published in IEEE Commun. Mag., vol. 36, no. 4, pp. 38-45, April 1998.)
Alternatively, if the measured distance variances are not available, or if the variances are assumed identical, a non-linear least squares (NLS) solution can be obtained by simply setting all the weights to unitary. However, solving the NLS problem requires an explicit minimization of a loss function, and hence necessitates using numerical search methods such as steepest descent or Gauss-Newton techniques. Such numerical search techniques are computationally costly and typically require a good initialization to avoid converging to a local minimum of the loss function. (See, e.g., the article “Mobile Positioning using Wireless Networks: Possibilities and Fundamental Limitations Based on Available Wireless Network Measurements” (“Gustafsson”), by F. Gustafsson and F. Gunnarsson, published in IEEE Sig. Proc. Mag., vol. 22, no. 4, pp. 41-53, July 2005.)
The article “The Interior-point Method for an Optimal Treatment of Bias in Trilateration Location” (“Kim”), by W. Kim, J. G. Lee, and G. I. Jee, published in IEEE Trans. Vehic. Technol., vol. 55, no. 4, pp. 1291-1301, July 2006, shows that, to obtain a closed-form solution and to avoid explicit minimization of the loss function, the set of expressions corresponding to each of the observations can be linearized using a Taylor series expansion. However, such an approach still requires an intermediate location estimate to obtain the Jacobian matrix. The intermediate location estimate required under this approach has to be sufficiently close to the true location of the MT for the linearity assumption to hold.
An alternative linear least squares (LLS) solution based on the measured distances was initially proposed in the article “A New Approach to the Geometry of TOA Location” (“Caffery II”), by J. J. Caffery, published in Proc. IEEE Vehic. Technol. Conf. (VTC), vol. 4, Boston, Mass., September 2000, pp. 1943-1949. Under that approach, one of the fixed terminals (FTs) is selected as a reference. The expressions corresponding to the measured distances of this reference FT is subtracted from the other (N−1) expressions to cancel the non-linear terms, where N denotes the number of observations. Eventually, once a linear set of expressions is obtained, a simple least squares (LS) matrix solution yields the location of the MT.
Variations of the LLS solution technique are also presented in the literature. For example, in the article “A Linear Programming Approach to NLOS Error Mitigation in Sensor Networks” (“Venkatesh”), by S. Venkatesh and R. M. Buehrer, published in Proc. IEEE IPSN, Nashville, Tenn., April 2006, multiple sets of linear expressions are obtained by selecting each of the FTs as a reference FT in turn and then proceeding as described in Caffery II. This procedure provides
      N    ⁡          (              N        -        1            )        2total number of unique equations, which are likely to yield a better location estimate, as compared to random selection of the reference FT.
Another example of the LLS solution technique is provided in the article “Robust Statistical Methods for Securing Wireless Localization in Sensor Networks” (“Li”), by Z. Li, W. Trappe, Y. Zhang, and B. Nath, published in Proc. IEEE Int. Symp. Information Processing in Sensor Networks (IPSN), Los Angeles, Calif., April 2005, pp. 91-98. Li proposes a different averaging technique. Under that technique, initially, the non-linear expressions are averaged over all the FTs. The resulting expression is then subtracted from the rest of the expressions to cancel out the non-linear terms. This averaging procedure yields N linear equations compared to (N−1) equations.
Another example of the LLS solution technique is provided in the article “On Impact of Topology and Cost Function on LSE Position Determination in Wireless Networks” (“Dizdarevic”), by V. Dizdarevic and K. Witrisal, published in Proc. Workshop on Positioning, Navigation, and Commun. (WPNC), Hannover, Germany, March 2006, pp. 129-138. In Dizderevic, the cost functions for LLS and NLS are compared using simulations, which show that NLS usually performs better than the LLS in most of the topologies. A similar result is also observed in Li, which clearly shows the sub-optimality of the LLS for position estimation.
While LLS is a sub-optimum location estimation technique, when reasonable position estimation accuracy is achieved, such a technique may be used to obtain the MT location, due to its lower implementation complexity, as compared to other iterative techniques (e.g., the NLS). Moreover, in other high-accuracy techniques (including the NLS approach and linearization based on the Taylor series), LLS can be used to obtain an initial location estimate for initiating the high-accuracy location algorithm (see, e.g., the article “Exact and Approximate Maximum Likelihood Localization Algorithms,” by Y. T. Chan, H. Y. C. Hang, and P. C. Ching, published in IEEE Trans. Vehicular Technology, vol. 55, no. 1, pp. 10-16, January 2006.). A good initialization may considerably decrease the computational complexity and eventual localization error of a high-accuracy technique. Therefore, improving the accuracy of the LLS localization technique is important for multiple reasons.
Under these methods, the reference FT is usually randomly selected. In addition, an averaging technique is employed for linearizing the set of expression. However, such averaging does not necessarily yield better accuracy, since undesirable FTs are also used as reference FTs in the linearization process. Furthermore, these prior art solutions do not consider the covariance matrix of decision variables after linearizing the system. This omission may lead to further inaccuracy, as even in LOS environments, the observations in the linear model may become correlated—a fact that is not expressly considered in the prior art. In NLOS environments, the effects of NLOS bias may also be mitigated if certain NLOS related its statistics are available. Prior art techniques use the weighted LS estimator typically with the assumption that the observations are independent. However, the observations in LLS may become correlated.
Therefore, for both LOS and NLOS conditions, a solution technique which (a) appropriately selects the reference FT based on the measurements, (b) incorporates the covariance matrix into the LLS solution, and (c) compensates for correlated observations using the covariance matrix of observations is desired.